﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.Hash
{
    //============================== 1002 查找常用字符
    //给定仅有小写字母组成的字符串数组A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。
    //例如，如果一个字符在每个字符串中出现3次，但不是4次，则需要在最终答案中包含该字符3次。
    class FindCommonCharacters
    {
        public IList<string> CommonChars(string[] words)
        {
            IList<string> result = new List<string>();
            if (words.Length == 0)
                return result;

            int[] hash = new int[26];//用来统计所有字符串里字符出现的最小频率
            for(int i = 0;i<words[0].Length;i++)//用第一个字符串给hash初始化
            {
                hash[words[0][i] - 'a']++;
            }
            //统计除第一个字符串外字符的出现频率
            for (int i =1;i<words.Length;i++)
            {
                int[] hashOtherStr = new int[26];
                for(int j = 0;j<words[i].Length;j++)
                {
                    hashOtherStr[words[i][j] - 'a']++;
                }
                //更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
                for(int k = 0;k<26;k++)
                {
                    hash[k] = Math.Min(hash[k], hashOtherStr[k]);
                }
            }
            //将hash统计的字符次数，转成输出形式
            for(int i = 0;i<26;i++)
            {
                while(hash[i] != 0)//这里使用while，多个重复的字符
                {
                    char c = (char)(i + 'a');
                    result.Add(c.ToString());
                    hash[i]--;
                }
            }
            return result;
        }
    }
}
